package com.chenyi.leetcode.editor.cn;
/**
 * [14]最长公共前缀
 * @author by chenyi
 * @className LongestCommonPrefix
 * @date 2022-06-16 00:31:44
 */
public class LongestCommonPrefix{
    public static void main(String[] args) {
        Solution solution = new LongestCommonPrefix().new Solution();
        // "dog","racecar","car"   "flower","flow","flight"
        System.out.println(solution.longestCommonPrefix1(new String[]{"flower","flow","flight"}));
    }
    @SuppressWarnings("AlibabaCommentsMustBeJavadocFormat")
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /**
         * 方法一：横向扫描
         * @param strs
         * @return
         */
        public String longestCommonPrefix(String[] strs) {
            if (strs == null || strs.length == 0) {
                return "";
            }

            String prefix = strs[0];
            for (int i = 1; i < strs.length; i++) {
                prefix = longestCommonPrefix(prefix, strs[i]);
                if (prefix.length() == 0) {
                    break;
                }
            }
            return prefix;
        }

        public String longestCommonPrefix(String str1, String str2) {
            int min = Math.min(str1.length(), str2.length());
            int index = 0;
            while (index < min && str1.charAt(index) == str2.charAt(index)) {
                index++;
            }
            return str1.substring(0, index);
        }

        /**
         * 方法二：纵向扫描
         * @param strs
         * @return
         */
        public String longestCommonPrefix1(String[] strs) {
            if (strs == null || strs.length == 0) {
                return "";
            }
            for (int i = 0; i < strs[0].length(); i++) {
                char c = strs[0].charAt(i);
                for (int j = 1; j < strs.length; j++) {
                    if (i == strs[j].length() || strs[j].charAt(i) != c) {
                        return strs[0].substring(0, i);
                    }
                }
            }
            return strs[0];
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}
